闲扯
据说这是一个套路题，果然我还是太嫩了呀。
题面
Solution
我们设 $E(i)$ 表示当前剩余生命值为 $i$ 时，英雄死亡的剩余步数，其中 $E(0)=0$ 。
我们将每一个 $E(i)$ 看做一个点，将它们之间的转移看做一条有向边，那么我们就可以得到一个图。
我们设 $f_i$ 表示每一轮中，英雄减少 $i$ 点生命值的概率。
我们有：
表示我们选了 $i$ 个来攻击英雄，剩余的随机攻击所有的随从。
设 $g_{i,j}$ 表示当前生命值为 $i$ ，生命值变成 $j$ 的概率。
- 对 $\forall i\in[1,n),j\in[1,i]$ ，我们有 $g_{i,j}=\frac{m}{m+1}f_{i-j}+\frac{1}{m+1}f_{i-j+1}$ 。
- 对 $\forall i\in[1,n),j=i+1$ ，我们有 $g_{i,j}=\frac{1}{m+1}f_{0}$ 。
- $g_{n,i}=f_{n-i}$ 。
那么，我们可以得到如下转移方程：
这显然不是一个 $DAG$ ，但是，我们可以发现，恰有有 $n$ 个未知数， $n$ 个方程，可以通过高斯消元来求解。
复杂度是 $O(n^3)$ 的，没法通过全部测试点。
但是可以发现这个矩阵很有特点，可以做到 $O(n^2)$ 求解。具体怎么做我也不知道
还有另外一种方法。
我们可以发现，第 $i$ 个方程，我们可以写成如下形式：
这就变成了由 $1\sim i$ 求出 $i+1$ 的形式了。
但是我们发现因为不知道 $E(1)$ ，所以我们没法推出剩余的值。
我们不妨设 $E(1)=x$ 。
那么我们可以推出 $E(i)=k_i\cdot x+b_i$ 。
由前 $n-1$ 个方程，我们可以推出 $E(n)=k_n\cdot x+b_n$ 。
而由第 $n$ 个方程，我们可以推出 $E(n)=k\cdot x+b$ 。
联立两个方程，求出 $x$ ，即可求出 $E(p)$ 。
特别的，如果 $k=0$ 或者 $k=1,n>1$ ，那么一定是打不死的，直接输出 $-1$ 即可。
Code
1 |
|